//
// Description: 304. 二维区域和检索 - 矩阵不可变
// Created by Loading on 2022/7/3.
//

#include <bits/stdc++.h>

using namespace std;

class NumMatrix {
public:
    explicit NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        pre.resize(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return pre[row2 + 1][col2 + 1] - pre[row2 + 1][col1] - pre[row1][col2 + 1] + pre[row1][col1];
    }

private:
    vector<vector<int>> pre;
};

int main() {
    vector<vector<int>> matrix{{3, 0, 1, 4, 2},
                               {5, 6, 3, 2, 1},
                               {1, 2, 0, 1, 5},
                               {4, 1, 0, 1, 7},
                               {1, 0, 3, 0, 5}};
    auto obj = new NumMatrix(matrix);

    int res1 = obj->sumRegion(2, 1, 4, 3);
    int res2 = obj->sumRegion(1, 1, 2, 2);
    int res3 = obj->sumRegion(1, 2, 2, 4);

    cout << res1 << ' ' << res2 << ' ' << res3 << endl;

    delete obj;

    return 0;
}
